1. Field of the Invention
The invention relates generally to data and image compression. More specifically, the invention relates to encoding for data and image compression, particularly where discrete wavelet transforms are utilized.
2. Description of the Related Art
One crucial aspect of imaging is the process of image compression. In digital systems such as digital cameras image compression is utilized to store and transmit a large amount of image information in fewest number of bits possible while still maintaining an image quality that is acceptable. One example of a popular image compression scheme is JPEG (Joint Photographic Experts Group) which is based upon the Discrete Cosine Transform (DCT). Recently, new image compression schemes have been developed utilizing the Discrete Wavelet Transform (DWT). Unlike the DCT which is periodic in nature, the DWT is better suited and often more efficient in representing sharp discontinuities in data such as that present in image edge features. The DWT is also capable of fast and efficient hardware implementation, particularly for small portable devices such as digital cameras. The DWT resolves an input image into a series of "sub-bands" which are shown in FIG. 1. The four sub-bands labeled LL, HL, LH and HH, where H in the sub-band designation refers to the application of a high-pass part of the DWT and L to the low-pass portion. The DWT sub-bands and their properties are discussed in greater detail below.
A process known as DPCM (Differential Pulse Code Modulation) may be utilized to encode and compress data whether first exposed to a DWT or not. In DPCM, the goal is to encode the difference (error value) between one pixel (or data value) and the predicted value using the neighboring pixels. In this manner, a highly correlated data set can be encoded with a fewer number of bits (smaller values) since the differences between one value and next are presumably small in comparison to the values themselves. With a poorly correlated or high entropy data set, the encoding efficiency of DPCM decreases since the difference values (without taking the absolute value) could be less easy to encode than the original data. For instance, if the each value in the data set has a possible range of 0 to n, the differential may range from -n to +n, which would take more bits to encode if this differential range were fully utilized. In imaging, the DPCM technique of encoding is particularly advantageous in that edge features, those regions of an image with sharply different pixel values that define the edge, are encoded using more information and visually less significant information (number of bits), such as a slight shade or tone difference is encoded using less bits. DPCM, as currently employed, is a serial operation in that as a row of image or image sub-plane is scanned, the values are encoded. The encoding of values involves the discovery of an error image (between one pixel and a neighboring pixel or predicted value for the neighboring pixel) and then an encoding of the original image pixel values and the error image based upon the error. Such a system is shown in FIG. 2 and is described in detail below. Where the error is between one pixel and predicted neighboring pixel, the DPCM technique is specifically referred to as "predictive" coding. Since most image arrays scan or obtain all the values in one row and then the next, the pixel data is compiled in a west-to-east direction. Due to the row-based scanning that imaging devices often employ, DPCM considers neighboring pixels to be east-west neighbors. When it is desired that north-south pixels (i.e., those belonging to different rows) are also to be considered for the error image, the technique of DPCM does so uniformly across all pixels in the image.
If an original image obtained from a image scan or from raw image data that is already stored uses DPCM, the arbitrary choice of a direction or set of directions for the error image generation is not easily avoided. However, where a DWT is first applied to the image data, the sub-band data rather than the original image should be encoded. In such an instance, there are features in the DWT which may aid in determining the best direction for error discovery during DPCM so that the encoded DWT image is smaller (uses even fewer bits) than would an arbitrary direction (or set of directions). Since a DWT processed image has certain predictable behavior in its sub-bands, this information can be exploited to reduce the size of the encoded image.
Thus, there is a need for a DPCM technique that is suited to and takes advantage of DWT behavior and is deliberate in the consideration of direction for error discovery and encoding.